On the Power of Multiplexing in Number-on-the-Forehead Protocols

摘要

We study the direct-sum problem for $k$-party ``Number On the Forehead''(NOF) deterministic communication complexity. We prove several positiveresults, showing that the complexity of computing a function $f$ in this model,on $\ell$ instances, may be significantly cheaper than $\ell$ times thecomplexity of computing $f$ on a single instance. Quite surprisingly, we showthat this is the case for ``most'' (boolean, $k$-argument) functions. We thenformalize two-types of sufficient conditions on a NOF protocol $Q$, for asingle instance, each of which guarantees some communication complexity savingswhen appropriately extending $Q$ to work on $\ell$ instances. One suchcondition refers to what each party needs to know about inputs of the otherparties, and the other condition, additionally, refers to the communicationpattern that the single-instance protocol $Q$ uses. In both cases, the toolthat we use is ``multiplexing'': we combine messages sent in parallelexecutions of protocols for a single instance, into a single message for themulti-instance (direct-sum) case, by xoring them with each other.